๐งท ๋ฐฐ์ด (Array)
๋์ผํ ์๋ฃํ์ ๋ฐ์ดํฐ๋ฅผ ์ฐ์๋ ๊ณต๊ฐ์ ์ ์ฅํ๊ธฐ ์ํ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ์ฐ๊ด๋ ๋ฐ์ดํฐ๋ฅผ ๊ทธ๋ฃนํํ์ฌ ๋ฌถ์ด์ค๋ค.
๐ช ์ฅ์
- ์ฐ๊ด๋ ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ณ์์ ์ ์ธ์ ์ค์ฌ์ค๋ค.
- ๋ฐ๋ณต๋ฌธ ๋ฑ์ ์ด์ฉํ์ฌ ๊ณ์ฐ ๊ณผ์ ์ ์ฝ๊ฒ ์ฒ๋ฆฌํ ์ ์๋ค.
int[] array = { 1,2,3,4,5,6 };
int arraySize = array.length;
๐ช ๋ฐฐ์ด ํ์ ํ๋ก๊ทธ๋จ
๊ธฐ๋ณธ์ ์ธ ํ์ ์๊ณ ๋ฆฌ์ฆ
tmp์ ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค์ ๊ฐ์ ์ ์ฅํ๊ณ , ๋๋จธ์ง ๊ฐ๋ค์ ํ ์นธ์ฉ ์์ผ๋ก ๋ก๊ฒจ์ ์ ์ฅํ๋ค.- ์ดํ
array[n]์tmp๊ฐ์ ์ ์ฅํ๋ค.
์ ๊ธ๋ง ์๊ณ ๋ฆฌ์ฆ
- ์ต๋๊ณต์ฝ์ gcd๋ฅผ ์ด์ฉํด ์งํฉ์ ๋๋์ด ์ฌ๋ฌ ์์๋ฅผ ํ๊บผ๋ฒ์ ์ด๋์ํจ๋ค.
- ์ฃผ์ด์ง ๋ฐฐ์ด์ด
int[] array = {1,2,3,4,5,6,7,8,9,10,11,12}๋ผ๋ฉด,1,2,3์ ๋ค๋ก ์ฎ๊ธธ ๋, ์ธ๋ฑ์ค๋ฅผ 3๊ฐ์ฉ ๋ฌถ๊ณ ํ์ ์ํค๋ ๋ฐฉ๋ฒ์ด๋ค. []arrary->{4,2,3,7,5,6,10,8,9,1,11,12}[]arrary->{4,5,3,7,8,6,10,11,9,1,2,12}[]arrary->{4,5,6,7,8,9,10,11,12,1,2,3}
์ญ์ ์๊ณ ๋ฆฌ์ฆ
- ํ์ ์ํค๋ ์์ ๋ํด ๊ตฌ๊ฐ์ ๋๋ reverse๋ก ๊ตฌํํ๋ค.
d=2 ์ด๋ฉด, ๊ตฌ๊ฐ์ 1,2 / 3,4,5,6,7 ๋ก ๋๋๋ค.
- ์ฒซ ๋ฒ์งธ ๊ตฌ๊ฐ
reverse-> 2,1 - ๋ ๋ฒ์งธ ๊ตฌ๊ฐ
reverse- > 7,6,5,4,3 - ํฉ์น๊ธฐ -> 2,1,7,6,5,4,3
- ํฉ์น ๋ฐฐ์ด์
reverse-> 3,4,5,6,7,1,2
void reverseArr(int[] array, int start, int end) {
while (start < end) {
int temp = array[start];
array[start] = array[end];
array[end] = temp;
start++;
end--;
}
}
void rotateLeft(int[] array, int d, int n) {
reverseArr(array, 0, d - 1);
reverseArr(array, d, n - 1);
reverseArr(array, 0, n - 1);
}
๐ช ๋ฐฐ์ด์ ํน์ ์ต๋ ํฉ ๊ตฌํ๊ธฐ
array[i] ๊ฐ ์์ ๋, i * array[i] ์ ํฉ์ด ๊ฐ์ฅ ํด ๋ ๊ทธ ๊ฐ์ ์ถ๋ ฅํ๊ธฐ
- ์ด๋ฅผ ํ์ ์ ํตํด ์ฐพ์ ์ ์๋ค.
// Input
array = { 1, 20, 2, 10 }
// Output
72
2๋ฒ ํ์ ํ์ ๋ ์๋์ ๊ฐ์ด ์ต๋๊ฐ์ด ๋์จ๋ค.
{ 2, 10, 1, 20 }
20 * 3 + 1 * 2 + 10 * 1 + 20 * 0 = 72
์ ๊ทผ๋ฒ
array[i]์ ์ ์ฒด ํฉ๊ณผi * array[i]์ ์ ์ฒด ํฉ์ ์ ์ฅํ ๋ณ์ ์ ์ธ- ์ต์ข
๊ฐ์ฅ ํฐ
sum๊ฐ์ ์ ์ฅํ ๋ณ์ ์ ์ธ - ๋ฐฐ์ด์ ํ์ ์ํค๋ฉด์
i * array[i]์ ํฉ ์ค ์ต๋๊ฐ์ ์ ์ฅํ๋ค.
ํด๊ฒฐ๋ฒ
- ํ์ ์์ด
i * array[i]์ sum์ ์ ์ฅํ ๊ฐ =R0 - 1๋ฒ ํ์ ํ๊ณ
i * array[i]์ sum์ ์ ์ฅํ ๊ฐ =R1 - ์ด ๋ ๊ฐ๋ฅผ ๋นผ๋ฉด
R1 - R0 = array[0] + array[1] + ... array[n - 2] - (n - 1) * array[n - 1] - ์ด๋ฅผ ๊ณ์ ๋ฐ๋ณตํ๋ค๋ณด๋ฉด,
Rj - R(j-1) = arrSum - n * array[n - j]๋ผ๋ ๊ท์น์ ์ป์ ์ ์๋ค.
int arrSum = ๋ฐฐ์ด์ ์ด ํฉ
int maxSum = ํ์ ์์ด ๊ตฌํ i * array[i]์ sum;
for (int j = 1; j < n; j++){
curSum = curSum + arrSum - n*arr[n-j];
if ( curSum > maxSum )
maxSum = curSum;
}
return maxSum;
๐ช ํน์ ๋ฐฐ์ด์ array[i] = i ๋ก ์ฌ๋ฐฐ์ด
์ฃผ์ด์ง ๋ฐฐ์ด์์ array[i] = i ๊ฐ ๊ฐ๋ฅํ ๊ฒ๋ง ์ฌ๋ฐฐ์ด์ํค๊ธฐ (array[i] = i ๊ฐ ์์ผ๋ฉด -1๋ก ์ฑ์ด๋ค.)
// Input
array = { -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 }
// Output
{ -1, 1, 2, 3, 4, -1, 6, -1, -1, 9 }
์ ๊ทผ๋ฒ
array[i] != -1&&array[i] != i๊ฐ ์ฐ์ ์กฐ๊ฑด- ํด๋น ๊ฐ์ ์ ์ฅ(
x)ํด๋๊ณ , ์ด ๊ฐ์ดx์ผ๋array[x]๋ฅผ ํ์ array[x]๊ฐ์ ์ ์ฅ(y)ํด๋๊ณ ,array[x]๊ฐ -1์ด ์๋๋ฉด์array[x]๊ฐx๊ฐ ์๋ ๋์์ ํ์array[x]๋ฅผx๊ฐ์ผ๋ก ์ ์ฅํด์ฃผ๊ณ , ๊ธฐ์กด์x๋ฅผy๋ก ์์
int fix(int[] array, int len) {
for (int i = 0; i < len; i++) {
if (array[i] != -1 && array[i] != i) {
int x = array[i];
while (array[x] != -1 && array[x] != x) {
int y = array[x];
array[x] = x;
x = y;
}
array[x] = x;
if (array[i] != i) array[i] = -1;
}
}
}